1. Field of the Invention
The present invention relates to cache data management in a computer system, and more particularly to a software methodology to control replacement of one or more selected pages within a cache memory in the computer system.
2. Description of the Related Art
Modern multiuser/multitasking computer systems run complex operating systems to accomplish concurrent executions of myriad user applications. Broadly speaking, an operating system may be defined as a system software that schedules tasks for execution by one or more processing units in the computer system, allocates storage among various application programs, handles the system interface to the peripheral hardware, and presents a default interface to the user when no application program is running. Some examples of operating systems include the ATandT UNIX operating system; the IBM OS/2 operating system; the Microsoft Windows family of operating systems and MS-DOS; the Macintosh operating system; the Novell Netware; and the Digital Equipment Corporation""s VMS operating system.
An operating system program may be divided into two parts: (1) the operating system kernel that contains the major operating system functions, such as the scheduler; and (2) various system programs which use facilities provided by the kernel to perform higher-level house-keeping tasks, such as providing an interface to various user application programs. An application program may be defined as a program that performs a specific function directly for the user (perhaps using one or more operating system services via the above mentioned interface). This is in contrast to system software, such as the operating system kernel, which supports the application programs. Word processing and spreadsheet software are common examples of popular application programs.
As used herein, the term xe2x80x9ctaskxe2x80x9d refers to a sequence of instructions arranged to perform a particular operation. Application software and the operating system may comprise one or more tasks.
In a typical multitasking operating system, memory management is usually employed for: (1) providing additional memory space when the physical memory space accessed by a processing unit is not large enough to hold all of the operating system and all of the application programs that are being executed by one or more users of the computer system; and (2) ensuring that executing tasks do not access protected areas of the physical system memory or those areas of the physical system memory allocated to other tasks. Generally, memory management may include allocating pages of physical memory for use by one or more tasks, mapping addresses generated by the tasks (xe2x80x9cvirtual addressesxe2x80x9d) to the allocated physical pages (xe2x80x9cphysical addressesxe2x80x9d) through an address translation mechanism, and deallocating pages released by a task.
A prior art system memory physical page allocation scheme is illustrated in FIG. 1. The computer system physical memory or system memory 12 may be visualized as being divided into a number of memory blocks or pages. Normally, the operating system kernel routines and relevant data as well as various software routines forming portions of one or more application programs being simultaneously executed by the operating system reside in the system memory 12, as respectively shown by the blocks numbered 11 and 13. The operating system software routines (block 11) and the application software (block 13) may require more than one memory page depending, among other things, on the page size and on the number of applications currently being executed.
During a program execution, a copy of a memory page 141 (i.e., the memory page 14) allocated to a program may be placed in the system cache memory 10. If the system cache memory 10 has no allocable space, then the system cache memory 10 may xe2x80x9cflush xe2x80x9d a corresponding page from the cache memory 10 to make space for the more recently accessed memory page 141. The cached page 14 typically contains a plurality of cache lines (or blocks), and caching is typically performed on a block by block basis rather than a page by page basis. Accordingly, caching a page actually involves caching the multiple cache lines of a page. Caching improves the rate of program execution by providing faster access for the processing unit to read data from/write data into the cached page 14 in the cache memory 10 during the corresponding application program execution.
It is understood that the cache memory space 16 of the cache memory 10 is typically smaller than that of the system memory 12. For example, when the cache memory space 16 is 1 MB in size and when the page size is 8 KB, the cache memory 10 may store up to 128 complete pages. However, the typical system memory physical space may be on the order of 64 MB, 80 MB, or even more. In that case, the system memory 12 may be visualized to contain 8192 or 10240 or more pages respectively. Further, it may not be desirable to increase the cache memory size 16 beyond a certain limit. In that event, the operating system may need to efficiently manage the resources of the cache memory 10 for a large number of applications that are currently under execution in the computer system.
When the user switches tasks or adds more applications for execution, the operating system may need to allocate one or more pages from the system memory 12 for the new tasks or applications. Under the prior art scheme of FIG. 1, the operating system uses a uniform method for allocating memory space, i.e., a request for a page of memory is allocated uniformly across the available memory space 20 according to any of the existing page allocation algorithms. This is illustrated in detail in FIG. 1.
The allocable memory space 20 may be considered to comprise two sections: (1) memory pages that map to the same cache memory storage locations as the cached page 14 when placed in the cache memory 10; and (2) the remaining memory pages, 15-1 through 15-N+2 and further, in the allocable memory space 20 that do not map to the same cache memory storage locations as the cached page 14. For the present discussion, the memory pages under (1) may be termed as conflict pages 18 and may be designated as conflict_page-1 (18-1) through conflict_page-N+2 (18-N+2) and onwards. The number of conflict pages depends on the size of the allocable physical memory space and on the size of the cache memory 10. In the previous example of the cache memory of 1MB size, the system memory of 80 MB can have a maximum of 79 conflict pages. The 80th xe2x80x9cconflict pagexe2x80x9d would be the cached page 141. In any event, the actual number of conflict pages may not be insubstantial. The memory pages under (2) may then be termed as non-conflict pages or free pages 15 (e.g., pages 15-1 through 15-N+2 and further) for the present discussion.
Under the uniform method of allocation mentioned above, the operating system may simply allocate a conflict page, e.g., the conflict_page-1 (18-1), after allocating the page 141. The same method is repeated when the need to allocate an additional system memory page arises. In that event, the operating system may again allocate another conflict page, e.g., the conflict_page-2 (18-2), after storing the conflict_page-1 into the appropriate memory location, i.e., the memory location 18-1. Unfortunately, allocating one or more conflict pages may cause the cached page 14 to be displaced from the cache memory 10 (when the conflict pages are accessed). Subsequent accesses to the page 141 may miss in the cache memory 10, increasing memory latency for the task to which the page 141 is allocated.
The increased latency described above is particularly a problem in that some data and text (i.e., instruction sequences) are frequently accessed and thus heavily limit access latency when not present in the cache. For the present discussion, these data may be referred to as xe2x80x9ccritical dataxe2x80x9d and may include not only data and text, but also various software routines, instruction codes or any other digital information already existing or being generated during an application program execution. The present operating system page allocation schemes may also cause a large number of conflict misses in the cache memory 10 when critical data is frequently replaced by other data or text that may have shorter cache lifetimes. Therefore, a method for efficient memory page allocation is desirable so as to maximize cache data reuse.
The foregoing described various problems that may frequently arise in case of the existing operating systems implementing a uniform method of physical system memory page allocation. The present invention contemplates a software methodology to control replacement of one or more selected pages within the cache memory in the computer system. In one embodiment of the present invention, the operating system is configured to designate a xe2x80x9chot pagexe2x80x9d within the physical system memory and to prevent the replacement of that hot page when placed within the cache memory during execution of various application programs. One criterion for selecting the hot page may be the existence of critical data within the hot page. In an alternative embodiment, the user may be allowed to designate one or more hot pages under the operating system control. However, the operating system may warn the user in the event that the number of hot pages placed within the cache memory exceeds a predetermined limit.
In one embodiment, the operating system inhibits allocation of the conflict pages that would map to the cache memory storage locations to which the hot page maps when cached. This may be accomplished by a sorted free list in the physical system memory where pages that would map to the same location as the hot page, i.e., the conflict pages, are placed at the bottom of the free list and the operating system may be configured to inhibit, to the extent possible, allocation of these conflict pages even if the system is paging. A pointer may be placed in the system memory for scanning the free list for allocable memory space. In one embodiment, the pointer may scan the free list from top to bottom (as pages are allocated) until a conflict page is reached. This may allow the operating system to prevent the conflict pages from getting cached to the hot page location within the cache memory.
In another embodiment, the compiler may mark critical data or text in a task that would remain in the cache while lightly used data in the task may be placed in those parts of the cache memory which may be replaced due to conflict misses. In a different embodiment, the operating system may be configured to establish the amount of conflicting page space within the free list ahead of time, i.e., prior to beginning the execution of one or more application programs. This may allow the operating system to efficiently identify the total allocable physical memory space beforehand and to accordingly allocate memory pages during program execution.
The present invention also contemplates a computer system whose operating system is configured to identify a plurality of hot pages within the system memory and to selectively prevent replacement of the plurality of hot pages during execution of one or more application programs. In a further embodiment, the present invention contemplates a storage medium that contains a cache data management program that is executable by a computer system when received from said storage medium and placed within a system memory in the computer system, and wherein upon execution said cache data management program designates a hot page within the system memory and identifies one or more conflict pages for that hot page. The cache data management program may also prevent the allocation of these conflict pages to one or more applications in the computer system. Alternatively, the cache data management program may configure the operating system to accomplish the desired controlled page allocation functionality.
The cache access times for critical data pages are thus improved through reduced access latencies. The efficient memory page allocation methodology according to the present invention thus allows for maximization in cache data reuse. Conflict misses in the cache are also prevented for selected memory pages.